package com.lw.leetcode.hash.c;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1982. 从子集的和还原数组
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/7 13:41
 */
public class RecoverArray {

    public static void main(String[] args) {
        RecoverArray test = new RecoverArray();

        // [1,2,-3]
        int n = 3;
        int[] sums = {-3, -2, -1, 0, 0, 1, 2, 3};

        // [0,0]
//        int n = 2;
//        int[] sums = {0, 0, 0, 0};

        // [0,-1,4,5]
//        int n = 4;
//        int[] sums = {0, 0, 5, 5, 4, -1, 4, 9, 9, -1, 4, 3, 4, 8, 3, 8};

        // [-45,-80,-182,276,296,-509,-653,721]
//        int n = 8;
//        int[] sums = {408, -307, 86, -886, -164, 784, -377, 49, -1424, 14, 0, 310, -589, 162, 735, 872, -80, 557, -590, -290, 319, -51, -1173, -715, 216, -1207, -392, 333, -437, 539, 276, 459, 522, -233, 527, 390, -472, -388, -521, -486, -1011, -457, -278, 596, -452, -62, -145, -262, -1048, -427, -852, -159, -402, 171, 264, 704, -1287, -210, -126, 345, 114, 1168, 443, -263, -119, -1389, -502, -347, -338, 117, 57, -880, 494, 378, -897, -733, 1066, 212, 1293, -623, 137, 488, 492, 37, -165, 508, -1128, -946, 201, 265, -639, 167, 364, 23, -960, 710, 770, -293, 261, 30, -635, -482, -509, -911, -15, 34, 284, -772, -327, -698, 997, -45, -441, -57, -206, 196, -343, 952, -915, 151, 231, 458, -114, 515, 82, 383, 1248, 428, 344, -668, -604, -227, 363, 595, 239, -817, 721, -308, -736, -161, 986, 306, -395, -691, -619, 972, -270, 51, -95, -415, -664, -199, 251, 296, -11, -539, -653, 414, -835, 892, -50, -460, -816, 659, -966, 102, 815, 602, -190, 326, -372, -81, 94, 87, 69, 131, -125, -258, -703, -12, -634, 1017, 560, -771, 755, -1242, -1068, -245, -866, 1213, -176, 219, -931, -182, 246, -31, 18, 1031, 68, -213, 299, -1162, 1111, 572, 63, -1469, -357, 690, 182, -358, -239, -1148, 226, 447, -559, -225, -540, -1113, -554, -584, -1344, 281, 477, -313, 917, -422, 132, -778, 790, -475, -244, -1093, -684, -991, 835, 463, -670, -495, 413, 641, 937, -17, -131, 739, 676, 181, -520, 640, -440, -96, 6, -194, -1193, -407, -566, -748};

        int[] ints = test.recoverArray(n, sums);
        System.out.println(Arrays.toString(ints));
    }

    private int[] values;

    public int[] recoverArray(int n, int[] sums) {
        int length = sums.length;
        if (length == 1) {
            return sums;
        }
        Arrays.sort(sums);
        values = new int[n];
        find(n, sums);
        return values;
    }

    private boolean find(int n, int[] sums) {
        int length = sums.length;
        if (length == 2) {
            values[0] = sums[0] == 0 ? sums[1] : sums[0];
            return true;
        }
        int t = sums[1] - sums[0];
        length >>= 1;
        n--;
        int[] arr = new int[length];
        if (contains(sums, t)) {
            boolean boo = check(sums, t, arr);
            if (boo && find(n, arr)) {
                values[n] = t;
                return true;
            }
        }
        t = -t;
        if (!contains(sums, t)) {
            return false;
        }
        values[n] = t;
        check(sums, t, arr);
        return find(n, arr);
    }

    private boolean contains(int[] sums, int t) {
        for (int sum : sums) {
            if (sum == t) {
                return true;
            }
        }
        return false;
    }

    private boolean check(int[] sums, int t, int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int sum : sums) {
            map.merge(sum, 1, (a, b) -> a + b);
        }
        boolean b = t < 0;
        int length = sums.length;
        int index = b ? arr.length - 1 : 0;
        int step = b ? -1 : 1;
        for (int i = 0; i < length; i++) {
            int sum = b ? sums[length - 1 - i] : sums[i];
            Integer c1 = map.get(sum);
            if (c1 == 0) {
                continue;
            }
            map.put(sum, c1 - 1);
            Integer c2 = map.get(sum + t);
            if (c2 == null || c2 == 0) {
                return false;
            }
            arr[index] = sum;
            index += step;
            map.put(sum + t, c2 - 1);
        }
        return true;
    }

}
